package com.sort;

import java.util.Arrays;

/**
 * 希尔排序：时间复杂度O(n*n)，空间复杂度O(1)，不稳定
 * <p>
 * 1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
 * 2.按增量序列个数k，对序列进行k 趟排序；
 * 3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
 * 仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 *
 * @author: keluosi@bicitech.cn
 * @review:
 * @date: 2018/9/28
 */
public class ShellSort {
    public static void sort(int[] a) {
        // 间隔序列
        int gap = 1;
        // 动态规范间隔序列
        while (gap < a.length / 3) {
            gap = gap * 3 + 1;
        }
        while ((gap /= 3) > 0) {
            for (int i = gap; i < a.length; i++) {
                int temp = a[i];
                int j = i - gap;
                for (; j >=0 && temp < a[j]; j-=gap) {
                    a[j+gap] = a[j];
                }
                a[j + gap] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {3, 2, 5, 4, 1, 7, 9, 6, 3, 11, 45, 32, 22, 1, 33, 42, 123, 22, 54, 54, 55, 76};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}
